Search
We can consider searching as an agent-based task, for which the agent finds a sequence of actions which transform the environment into the goal state.
Open loop search
While the agent executes the solution, it ignores the perception stage.
This is possible if the environment is:
- Deterministic
- Fully observable
- Known to the agent
This is not possible with chess, because the other player can change the environment, so we must perceive it again.
Search problem definition
We have a State Space(set) which contains all the possible states of the environment.
We have a Successor function that maps actions to their cost.
We also have a Start state and a Goal state.
State Space Graph
A mathematical representation of a search problem.
In this graph:
- Nodes == world states
- Edges == successors
- Each state is unique
- The goal is a set of goal nodes
- Sometimes edges are one-way
Tree search
- Root node == start state
- Children nodes == successors
- Nodes == plans(set of actions)
For tree search problems we have:
- A frontier: which is the set of nodes that we can potentially expand to.
- A strategy, which is the rule that makes us choose which nodes to expand from the frontier.
- The goal state.
Performance of search
The algorithm is ... if ...:
- Complete: if it is guaranteed to find a solution.
- Optimal: if it is guaranteed to find the least cost path.
Then we also have:
- Time complexity: is the amount of nodes that we need to traverse.
- Space complexity: is the amount of nodes that we need to keep in memory.
Time/Space Complexity variables
In order to continue, we need to define some variables:
- b: maximum branching factor of search tree.
- d: depth of the shallowest goal node.
- m: maximum length of any path in the state space
Breadth-first Search
The strategy for this tree search is: Always expand shallowest node.
- Is it complete? Yes, we are guaranteed to find a solution if b is finite.
- Time complexity:
- Space complexity:
- Is it Optimal? Yes, but only if cost = 1 for each step.
Depth-first Search
The strategy for this tree search is: Always expand deepest node.
- Is it complete? No, it fails in infinite depth or looped spaces.
- Time complexity:
- Space complexity:
- Is it optimal? No lol. We could find sub-optimal before finding optimal.
Iterative deepening?
From this point on, nodes can have different costs.
Uniform Cost Search
The strategy for this tree search is: Always expand to the cheapest node.
We basically order the frontier by the path cost function for each node. Then we expand on the first one.
Greedy
Expand node closest to goal according to a heuristic function.
A*
Expand node that has lower cost according to this cost function
